package PersonStu.sanqi;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @Author by KoVaVo
 * @Date 2023-01-03 22:26
 * @Desc:
 * 有N台咖啡机，数组中每个数字代表咖啡机生产1杯咖啡的时间，咖啡机只能串行生产。
 * 有M个人，求每个人最早获取咖啡的时间（或者每台咖啡机能够搞定多少个人）？
 * 思路：使用的数据结构=》使用优先队列构建一个小根堆，
 */
public class code_27_Coffee {

    public static class coffeeMachine{
        int start;
        int work;

        public coffeeMachine(int s,int w){
            this.start = s;
            this.work = w;
        }
    }

    //构建小根堆
    public static class CoffeeMachineComparator implements Comparator<coffeeMachine>{
        @Override
        public int compare(coffeeMachine o1, coffeeMachine o2) {
            return o1.start + o1.work - o2.work - o2.start;
        }
    }

    /**
     *
     * @param arr ： 代表的是每台咖啡机生产1杯咖啡所用的时间
     * @param M ： 有M 个人
     * @return
     */
    public static int [] CoffeChoice(int[] arr, int M){
        int[] ans = new int[M];
        PriorityQueue<coffeeMachine> heap = new PriorityQueue<>(new CoffeeMachineComparator());
        //在最开始的时候想堆中start=0位置填充数据。
        for (int coffee : arr) {
            heap.add(new coffeeMachine(0,coffee));
        }
        //
        for (int i = 0; i < M; i++) {
            //将堆中的第一个弹出
            coffeeMachine coffee = heap.poll();
            //填充ans的对应的位置。
            ans[i] = coffee.start + coffee.work;
            //累加弹出的start+work 就是下一次要放到堆中的开始的时间
            coffee.start = ans[i];
            //将下一条的数据放到小根堆中
            heap.add(coffee);
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] arr = {3,1,7};
        int num = 10;
        int[] ints = CoffeChoice(arr, num);
        System.out.println(Arrays.toString(ints));
    }
}
